package week_09;

/**
 * 36. 有效的数独
 * 请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
 * <p>
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 * <p>
 * 注意：
 * <p>
 * 一个有效的数独（部分已被填充）不一定是可解的。
 * 只需要根据以上规则，验证已经填入的数字是否有效即可。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：board =
 * [['5','3','.','.','7','.','.','.','.']
 * ,['6','.','.','1','9','5','.','.','.']
 * ,['.','9','8','.','.','.','.','6','.']
 * ,['8','.','.','.','6','.','.','.','3']
 * ,['4','.','.','8','.','3','.','.','1']
 * ,['7','.','.','.','2','.','.','.','6']
 * ,['.','6','.','.','.','.','2','8','.']
 * ,['.','.','.','4','1','9','.','.','5']
 * ,['.','.','.','.','8','.','.','7','9']]
 * 输出：true
 * 示例 2：
 * <p>
 * 输入：board =
 * [['8','3','.','.','7','.','.','.','.']
 * ,['6','.','.','1','9','5','.','.','.']
 * ,['.','9','8','.','.','.','.','6','.']
 * ,['8','.','.','.','6','.','.','.','3']
 * ,['4','.','.','8','.','3','.','.','1']
 * ,['7','.','.','.','2','.','.','.','6']
 * ,['.','6','.','.','.','.','2','8','.']
 * ,['.','.','.','4','1','9','.','.','5']
 * ,['.','.','.','.','8','.','.','7','9']]
 * 输出：false
 * 解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
 * 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
 */
public class ValidSudoku_36 {


    public boolean isValidSudoku(char[][] board) {
        // 判断有没有效 是否可解 N * M 的二维数组
        // 每一个位置可以hash 一个 i*n+j
        // 对该数验证是否合法:
        // 同一行 同一列 同一个3*3 小方格是否重复
        // 我自己的思路使用了3个for循环来控制判断
        // 可以用三个二维数组来实现判断
        int[][] rows = new int[9][10];
        int[][] cols = new int[9][10];
        int[][] box = new int[9][10];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int k = board[i][j] - '0';
                    int boxid = i / 3 * 3 + j / 3;
                    if (rows[i][k] == 1) return false;
                    if (cols[j][k] == 1) return false;
                    if (box[boxid][k] == 1) return false;
                    rows[i][k] = 1;
                    cols[j][k] = 1;
                    box[boxid][k] = 1;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        char[][] arr = new char[][]{
                {'.', '.', '5', '.', '.', '.', '.', '.', '6'},
                {'.', '.', '.', '.', '1', '4', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '9', '2', '.', '.'},
                {'5', '.', '.', '.', '.', '2', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '3', '.'},
                {'.', '.', '.', '5', '4', '.', '.', '.', '.'},
                {'3', '.', '.', '.', '.', '.', '4', '2', '.'},
                {'.', '.', '.', '2', '7', '.', '6', '.', '.'}

        };
        ValidSudoku_36 test = new ValidSudoku_36();
        System.out.println(test.isValidSudoku(arr));
    }
}
